This invention relates generally to cache replacement algorithms, and more particularly to providing a generalized least recently used algorithm that accepts visually-intuitive configuration input, implemented for the purpose of cache performance analysis.
Cache algorithms (or replacement algorithms) are information optimizing instructions that that are implemented within computing systems for the management of stored cache information. Since cache sizes are usually limited by design when a cache is full algorithms are utilized to ascertain which cache items are to be discarded in order to make room for new items. To ensure the optimized performance of a cache it is desirable to have a cache algorithm discard any items that are least likely to be utilized for the longest period of time in the future.
A least recently used (LRU) algorithm is an example of a replacement algorithm that discards the least recently used item first within a cache. In general, a LRU replacement algorithm monitors and maintains age bits for cache lines and through the use of these age bits, it selects the least recently used line within a cache. Functionally, in the event that a cache line is used then the age-bits for every other associated cache line is changed. LRU algorithms implemented for line replacement for each level of cache are tailored to a specific cache design. Therefore, a cache performance model must readily implement any standard or non-standard LRU scheme in order to identify the optimal implementation for a given design, and further, be capable of reporting how far an implemented scheme is from ideal.